package Leetcode.Stack;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;

/**
 * @Author: kirito
 * @Date: 2024/4/17 13:28
 * @Description:
 * 队列中可以看到的人数
 * 已解答
 * 困难
 * 相关标签
 * 相关企业
 * 提示
 * 有 n 个人排成一个队列，从左到右 编号为 0 到 n - 1 。给你以一个整数数组 heights ，每个整数 互不相同，heights[i] 表示第 i 个人的高度。
 *
 * 一个人能 看到 他右边另一个人的条件是这两人之间的所有人都比他们两人 矮 。更正式的，第 i 个人能看到第 j 个人的条件是 i < j 且 min(heights[i], heights[j]) > max(heights[i+1], heights[i+2], ..., heights[j-1]) 。
 *
 * 请你返回一个长度为 n 的数组 answer ，其中 answer[i] 是第 i 个人在他右侧队列中能 看到 的 人数 。
 *
 *
 *
 * 示例 1：
 *
 *
 *
 * 输入：heights = [10,6,8,5,11,9]
 * 输出：[3,1,2,1,1,0]
 * 解释：
 * 第 0 个人能看到编号为 1 ，2 和 4 的人。
 * 第 1 个人能看到编号为 2 的人。
 * 第 2 个人能看到编号为 3 和 4 的人。
 * 第 3 个人能看到编号为 4 的人。
 * 第 4 个人能看到编号为 5 的人。
 * 第 5 个人谁也看不到因为他右边没人。
 * 示例 2：
 *
 * 输入：heights = [5,1,2,3,10]
 * 输出：[4,1,1,1,0]
 *
 *
 * 提示：
 *
 * n == heights.length
 * 1 <= n <= 105
 * 1 <= heights[i] <= 105
 * heights 中所有数 互不相同 。
 */

public class canSeePersonsCount {
    public static void main(String[] args) {
        int[] heights = {5,1,2,3,10};
        System.out.println(Arrays.toString(canSeePersonsCount(heights)));
//        System.out.println(checkDecreasingSubsequence(heights,0,4));

    }
    /**
     * 1.暴力找思路
     *      left起点，right中，如果left到right中间的高度都比她两矮，那么ans[i]+1
     * @param heights
     * @return
     */
    public static int[] canSeePersonsCount(int[] heights) {
        int len = heights.length;
        int[] ans = new int[len];
        for (int left = 0; left < len - 1; left++) {
            for (int right = left + 1; right <len; right++) {
                if (checkDecreasingSubsequence(heights, left, right)) {
                    ans[left]++;
                }
            }
            if (ans[left] == 0) {
                ans[left]++;
            }
        }
        return ans;
    }

    public static boolean checkDecreasingSubsequence(int[] nums, int i, int j) {
        // 检查i和j的有效性
        if (i < 0 || i >= nums.length || j <= i || j > nums.length) {
            return false;
        }

        // 如果j=i+1，只需要检查nums[j]是否小于nums[i]
        if (j == i + 1) {
            return nums[j] < nums[i];
        }

        // 从i+1到j-1遍历，检查所有元素是否都小于nums[i]和nums[j]
        for (int k = i + 1; k < j; k++) {
            if (nums[k] >= nums[i] || nums[k] >= nums[j]) {
                return false;
            }
        }

        return true;
    }

    /**
     *
     * @param heights
     * @return
     */
    public static int[] canSeePersonsCount2(int[] heights) {
        int n = heights.length;
        int[] ans = new int[n];
        //栈里边存的是递增序列
        Deque<Integer> st = new ArrayDeque<>();
        for (int i = n - 1; i >= 0; i--) {
            while (!st.isEmpty() && st.peek() < heights[i]) {
                st.pop();
                ans[i]++;
            }
            if (!st.isEmpty()) { // 还可以再看到一个人
                ans[i]++;
            }
            st.push(heights[i]);
        }
        return ans;
    }
}
